package com.zxy.javaarithmetic.LinearList;

import com.zxy.javaarithmetic.Utils;

/**
 * @author : Shonn.Zhang
 * @email : shonn.zhang@mart.blue
 * @time : 2021/8/27 15:27
 * @desc : 二分查找及其变种
 */
public class BinarySearchDemo {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 6,6,6,6, 8, 9, 10};
        Utils.print(arr);
        System.out.println("search first 6 index = " + binarySearch3(arr,7));
    }

    /**
     * 简单二分查找
     *
     * @param arr   数组，不存在重复元素
     * @param val   要查询的数
     * @return
     */
    private static int binarySearch(int[] arr, int val) {
        int low = 0, high = arr.length - 1, mid;

        while (low <= high) {
            mid = low + ((high - low) >> 1);
            if (val == arr[mid]) {
                return mid;
            } else if (val < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return -1;
    }

    /**
     * 查找第一个（或最后一个）等于给定值的元素
     * @param arr  数组，存在重复元素
     * @param val
     * @return
     */
    private static int binarySearch1(int[] arr,int val){
        int low = 0, high = arr.length - 1,mid;

        while (low <= high){
            mid = low + ((high - low) >> 1);
            if(val < arr[mid]){
                high = mid - 1;
            }else if(val > arr[mid]){
                low = mid + 1;
            }else {
                //判断当前是否是第一个等于val的元素
                if(mid == 0 || arr[mid - 1] != val){
                    return mid;
                }else {
                    high = mid - 1;
                }

//                //判断当前值是否是最后一个等于val的元素
//                if(mid == (arr.length-1) || arr[mid+1] != val){
//                    return mid;
//                }else {
//                    low = mid + 1;
//                }
            }
        }
        return -1;
    }

    /**
     * 查找第一个大于等于给定值的元素
     * @param arr
     * @param val
     * @return
     */
    private static int binarySearch2(int[] arr, int val){
        int low = 0,high = arr.length - 1,mid;

        while (low <= high){
            mid = low + ((high - low) >> 1);
            if(val > arr[mid]){
                low = mid + 1;
            }else {
                if(mid == 0 || arr[mid-1] < val){
                    return mid;
                }else {
                    high = mid - 1;
                }
            }
        }

        return -1;
    }

    /**
     * 查找最后一个小于等于给定值的元素
     * @param arr
     * @param val
     * @return
     */
    private static int binarySearch3(int[] arr, int val){
        int low = 0,high = arr.length,mid;
        while (low <= high){
            mid = low + ((high - low) >> 1);
            if(val < arr[mid]){
                high = mid - 1;
            }else {
                if(mid == (arr.length -1) || arr[mid + 1] > val){
                    return mid;
                }else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }

}
